/*
 * @lc app=leetcode.cn id=9 lang=cpp
 *
 * [9] 回文数
 *
 * https://leetcode-cn.com/problems/palindrome-number/description/
 *
 * algorithms
 * Easy (56.00%)
 * Total Accepted:    78.2K
 * Total Submissions: 139.7K
 * Testcase Example:  '121'
 *
 * 判断一个整数是否是回文数。回文数是指正序（从左向右）和倒序（从右向左）读都是一样的整数。
 * 
 * 示例 1:
 * 
 * 输入: 121
 * 输出: true
 * 
 * 
 * 示例 2:
 * 
 * 输入: -121
 * 输出: false
 * 解释: 从左向右读, 为 -121 。 从右向左读, 为 121- 。因此它不是一个回文数。
 * 
 * 
 * 示例 3:
 * 
 * 输入: 10
 * 输出: false
 * 解释: 从右向左读, 为 01 。因此它不是一个回文数。
 * 
 * 
 * 进阶:
 * 
 * 你能不将整数转为字符串来解决这个问题吗？
 * 
 */
#include <iostream>

class Solution {
public:
    bool isPalindrome(int x) {
        // x为负数的时候不可能是回文数，末位为0的时候不可能是回文数（0除外）
        if( x < 0 || (x % 10 == 0 && x != 0))
            return false;
        int temp = x;
        // 1、将整数翻转然后判断与之前的数的大小是否相等,但是会有整数溢出的危险
        int value = 0;
        int n = 0;
        while(temp != 0){
            n = temp % 10;
            value = n + value * 10;
            temp = temp / 10;
        }
        if(x == value)
            return true;
        return false;
    }

    bool isPalindrome_leetCode(int x) {
        // 将整数的一半进行翻转，与剩余的另一半进行比较，如果相等则是回文数
        // 如何判断需要翻转的一半的数字的是第几位？
        // leetcode提供的解法是，当翻转的数比未翻转的数大时，那么就可以判断已经翻转了一半的数字
        if( x < 0 || (x % 10 == 0 && x != 0))
            return false;
        int value = 0;
        while(x > value) {
            value = value * 10 + x % 10;
            x = x / 10;
        }
        return value == x || value / 10 == x; 
        
    }
};

int main(int agrc, char* argv[]){
    Solution slu;
    int n1 = 123321; // true
    int n2 = -123321; // false
    int n3 = 121; //true
    int n4 = 1; // true
    int n5 = 12345; //false
    int n6 = 10; // false

    std::cout<<slu.isPalindrome(n1)<<std::endl;
    std::cout<<slu.isPalindrome(n2)<<std::endl;
    std::cout<<slu.isPalindrome(n3)<<std::endl;
    std::cout<<slu.isPalindrome(n4)<<std::endl;
    std::cout<<slu.isPalindrome(n5)<<std::endl;
    std::cout<<slu.isPalindrome(n6)<<std::endl;

    std::cout<<"leetcode"<<std::endl;
    std::cout<<slu.isPalindrome_leetCode(n1)<<std::endl;
    std::cout<<slu.isPalindrome_leetCode(n2)<<std::endl;
    std::cout<<slu.isPalindrome_leetCode(n3)<<std::endl;
    std::cout<<slu.isPalindrome_leetCode(n4)<<std::endl;
    std::cout<<slu.isPalindrome_leetCode(n5)<<std::endl;
    std::cout<<slu.isPalindrome_leetCode(n6)<<std::endl;

    getchar();
}

